#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1e6+10;

bool st[N];
int prime[N],cnt;
int res[N];
void init()
{
	int n=N-1;
	for(int i=2;i<=n;i++)
	{
		if(!st[i])
			prime[cnt++]=i;
		for(int j=0;j<cnt && prime[j]<=n/i;j++)
		{
			st[prime[j]*i]=true;
			if(i%prime[j]==0)
				break;
		}
	}
}
int main()
{
	int n;
	cin>>n;
	init();
	for(int i=0;i<cnt;i++)
	{
		int t=0;
		int c=1;
		while(pow(prime[i],c)<=n)
		{
			t+=n/pow(prime[i],c);
			c++;
		}
		if(t!=0)
			cout<<prime[i]<<' '<<t<<endl;
	}
	return 0;
}
